import java.util.*;

public class TopKFrequentElements {
    /*
    * 前 K 个高频元素
    * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
    *
    * 提示：
    * 1 <= nums.length <= 10(5)
    * k 的取值范围是 [1, 数组中不相同的元素的个数]
    * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
    * */
    public static void main(String[] args){

    }

    // 我的想法：统计频数的话可以用hashmap
    // 显然，用sort排序，时间空间消耗不理想
    public int[] mySolution(int[] nums, int k){
        int[] res = new int[k];
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int value = hashMap.getOrDefault(nums[i], 0);
            hashMap.put(nums[i], value+1);
        }
        ArrayList<Map.Entry<Integer, Integer>> entries = new ArrayList<>(hashMap.entrySet());
        entries.sort((o1, o2) -> o2.getValue() - o1.getValue());
        for (int i = 0; i < k; i++) {
            res[i] = entries.get(i).getKey();
        }
        return res;
    }

    // 小顶堆排序
    public int[] solution(int[] nums, int k){
        int[] res = new int[k];
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p[1]));
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()){
            if(pq.size() < k)   // 不满k个，直接加进去
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            else {
                if(entry.getValue() > pq.peek()[1]){
                    pq.poll(); // 因为是小顶堆，顶最小，遇到大的就把顶弹出去，再把大的加进来
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll()[0];
        }
        return res;
    }

    // 大顶堆排序(最快)
    public int[] solution1(int[] nums, int k){
        int[] res = new int[k];
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums){
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()){
            // 大顶堆，最大的就在顶上，直接加就好了
            pq.add(entry);
        }
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll().getKey();
        }
        return res;
    }


}
